package com.asia.algorithmcode.backTracking;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @DESCRIPTION: 77
 * @USER: wanfu
 * @DATE: 2025/3/25 星期二 14:58
 */
public class Combine {


    public static void main(String[] args) {
        List<List<Integer>> combine = new Combine().combine(4, 2);
        for (List<Integer> integers : combine) {
            for (Integer integer : integers) {
                System.out.print(integer + "\t");
            }
            System.out.println();
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> resList = new ArrayList<>();
        List<Integer> tempList = new ArrayList<>();
        traceBack(1, n, k, resList, tempList);

        return resList;
    }

    private void traceBack(int index, int n, int k, List<List<Integer>> resList, List<Integer> tempList) {
        if (tempList.size() + (n - index + 1) < k){
            return;
        }
        if (tempList.size() == k) {
            resList.add(new ArrayList<>(tempList));
            return;
        }

        tempList.add(index);
        traceBack(index + 1, n, k, resList, tempList);
        tempList.remove(tempList.size() - 1);
        traceBack(index + 1, n, k, resList, tempList);
    }

}
